package offerv1;

import java.util.ArrayList;
import java.util.List;

public class Offer21 {

    //1.双重循环暴力解
    //2.使用两个数组记录，最后合并
    public int[] exchange(int[] nums) {
        int n = nums.length, count = 0;
        List<Integer> list = new ArrayList<>();
        //奇数完成
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 1) {
                nums[i - count] = nums[i];
            } else {
                count++;
                list.add(nums[i]);
            }
        }
        int size = list.size();
        //n=4 size=2
        //偶数
        for (int i = n - size, j = 0; i < n; i++, j++) {
            nums[i] = list.get(j);
        }

        return nums;
    }
}

class Answer21 {
    public int[] exchange(int[] nums) {
        int i = 0, j = nums.length - 1, tmp;
        while (i < j) {
            //奇数
            while (i < j && (nums[i] & 1) == 1) i++;
            //偶数
            while (i < j && (nums[j] & 1) == 0) j--;
            //swap
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}
